#include"../include.h"

//删除字符串相邻重复项
//输入：s = "abbacdd"
//输出：c
string LeeCode_01()
{
    string S="abbacbbcj";
    int top = 0;                    //原地算法构建栈
    for (char ch : S) 
    {                               //top指向栈顶，同时代表 栈元素数量
        if (top == 0 || S[top - 1] != ch) //若栈为空或者当前元素与栈顶元素不相同，则入栈，数量加一
        {
            S[top++] = ch;
        } 
        else                        //当前元素ch与栈顶元素相同时，栈顶元素出栈，数量减一 
        {
            top--;
        }
    }
    S.resize(top);                  //最后根据栈顶top调整栈容量，去除其他无关元素
    return S;
}

//基本计算器II
//输入：s = "3+2*2"
//输出：7
int LeeCode_02(string s)
{
    int n=0,ls=1,ol,total=0;     // n表示当前数字 total表示最后结果，ol记录上一个数，ls循环次数
    char symbol='+';            // symbol记录上一个符号
    for(char ch:s)
    {                            // isdigit（）判断字符内容是否为整形变量，是则返回true
        if(isdigit(ch))          //判断是否为数字
        {                          // int(ch-'0')将字符内容转化为整形，n*10表示多位数的进位
            n=n*10+int(ch-'0');
        }                          //判断是否为符号，或者遍历到最后一个时，进行操作
        if((!isdigit(ch)&&ch!=' ')||ls>=s.length())
        {                               // 如果是乘号则说明total在前面已经多加了一个，需要去掉
            if(symbol=='*'||symbol=='/')
            {
                total-=ol;
            }
            switch(symbol)
            {
                case '+':ol=n;break;      // 加号直接计入总和
                case '-':ol=-n;break;     // 减号取相反数计入总和
                case '*':ol*=n;break;     // 乘号则将上一个数与当前数相乘，然后计入总和
                case '/':ol/n;break;      // 除号则将上一个数与当前数相除，然后计入总和
            }
            total+=ol;            //将每次计算后的数相加，遇到乘除要先减去最后加的数
            symbol=ch;            //然后将经过乘除运算的新结果加入进来
            n=0;                  //读取到符号的时候，则说明一个数字读取完毕
        }                         //n置零重新读取下一个数字
        ls++;                     //ls记录循环次数
    }
    return total;
}


/*
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
验证二叉树的前序序列化
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 
*/

bool LeeCode_03(string preorder)
{
    int n=0;        //  所有的叶子节点都是# 二叉树性质 叶子节点的总和比非叶子节点数多一
    for(int i=preorder.size()-1;i>=0;i--)//从后面往前数，方便脱去叶子节点，后续也容易操作容易理解
    {               //  所以根为#的节点数比为数字的节点数多一个
        if(preorder[i]==',')        // 逗号不用处理直接跳过
        {           // 每两个#，就脱去一个数字根，也就是脱去一个子树，同时用一个#补进去，标记为空
            continue;
        }
        if(preorder[i]=='#')        //记录下 根为#的节点数
        {
            n++;
        }
        else        // 根为数字的情况
        {
            while(i<preorder.size()&&preorder[i]!=',')
            {
                i--;         // 数字可能不是个位数，可能是多位数，直到读取','  才算是读取完一个数
            }
            if(n>=2)    // 虽然每两个# 脱去一个数字再补上一个数字，相当于只去掉一个#
            {
                n--;    // 但仍然要有两个#的时候才能去除
            }
            else        // 如果找到一个数字，但它后面不足两个#，就无法构成二叉树
            {
                return false;
            }
        }
    }
    if(n==1)    // 最后叶子节点减去非叶子节点，为一时则为真
    {
        return true;
    }
    else
    {
        return false;
    }
}


/*
螺旋矩阵II
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
*/
vector<vector<int>> LeeCode_04(int n)
{
    vector<vector<int>>v(n,vector<int>(n));     //构建二维矩阵
    int left=0,right=n-1,top=0,bottom=n-1;      //定义四个变量表示矩阵的四条边界
    int log=1;
    while(log<=n*n)
    {                       // 先往右推，推到边界的时候停止(i==right)，开始往下推
        for(int i=left;i<=right;i++)
        {
            v[top][i]=log++;
        }                   // 往下推要从top-1行开始，第一行已经在上面赋值过了，i==bottom时停止
        for(int i=top+1;i<=bottom;i++)
        {
            v[i][right]=log++;
        }                   // 往左推要从right-1列开始，最后一列的数在上面已经赋值，i==left时结束
        for(int i=right-1;i>=left;i--)
        {
            v[bottom][i]=log++;
        }  // 往上推同上，从bottom-1行开始，但此时结束条件为i=top-1，top行该列的数据最开始就赋值了
        for(int i=bottom-1;i>top;i--)
        {
            v[i][left]=log++;
        }               // 上述推完一圈，即缩小边界一圈，之后继续逆时针推，直到推完整个方阵
        left++;
        right--;
        top++;
        bottom--;
    }
    return v;
}


/*
不同的子序列    (初始动态规划)
要找出 f[n]=f[n-1]+f[n-2] 类似于前后项的关系 --关键
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
输入：s = "babgbag", t = "bag"
输出：5
v[i][j]代表t[j:]作为子序列在s[i:]中的个数
因为空字符串是所有字符串的子串，所以在v[i][t.size()]这一列都为 1
当s[i]==t[j]时，v[i][j]=v[i+1][j+1]+v[i+1][j]
当s[i]！=t[j]时，v[i][j]=v[i+1][j]
对于动态规划问题，建议用EXC列表一下，容易理解
*/
int LeeCode_05(string s, string t) 
{                                       //建立二维数组
    vector<vector<long>>v(s.size()+1,vector<long>(t.size()+1));
    for(int i=0;i<=s.size();++i)
    {                               // 填充空字符串的那一列
        v[i][t.size()]=1;
    }
    for(int i=s.size()-1;i>=0;i--)
    {
        for(int j=t.size()-1;j>=0;j--)
        {
            if(s[i]==t[j])               // 两个字符匹配时
            {
                v[i][j]=v[i+1][j+1]+v[i+1][j];
            }
            else                        // 两个字符不匹配时
            {
                v[i][j]=v[i+1][j];
            }
        }
    }                               // 返回比较最充分的位置的值
    return v[0][0];
}


/*
反转链表II
给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right
请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
1.栈解法
将要反转的数据截取下来，压栈，后依次出栈，改变链表数据域的值，达到反转目的
2.穿针引线(不修改节点的值，改变节点的next域指针指向达到反转目的)
*/
//栈方法
ListNode* LeeCode_0601(ListNode* head, int left, int right) 
{                       // l指向要开始反转的第一个元素，lo用来遍历从开头到right，保留下head方便返回
    ListNode *l,*lo=head;
    stack<int>s;        // 建立栈
    for(int i=1;i<=right;i++)   // 第一次从头遍历到right结点，取出要反转的区间，压栈
    {
        if(i>=left)
        {
            if(i==left)
            {
                l=lo;           // 记录要反转区间的起始地址
            }
            s.push(lo->val);
        }
        lo=lo->next;
    }
    for(int i=left;i<=right;i++)
    {
        l->val=s.top();         // 依次出栈，改变节点的值，达到反转
        s.pop();
        l=l->next;
    }
    return head;
}
// 穿针引线方法，(改变next域指向，不改变节点的值)
//   pre->1    cur->2   next->3   4
ListNode* LeeCode_0602(ListNode* head, int left, int right)
{
    ListNode *dummyNode = new ListNode(-1);   // 设置一个头节点
    dummyNode->next = head;
    ListNode *pre = dummyNode;       // pre指向第一个要反转元素的前一个节点
    for (int i = 0; i < left - 1; i++) 
    {                         // 遍历链表，找到第一个要反转的元素的前一个节点，pre指向它
        pre = pre->next;
    }                       // cur指向反转起始区间的第一个元素，反转后，指向反转区间的最后一个元素
    ListNode *cur = pre->next;
    ListNode *next;         // next起中间变量的作用，指向新遇到的节点
    for (int i = 0; i < right - left; i++) //   pre->1    cur->2   next->3   4
    {                       // 每次把新遇到的元素放到第一，执行到区间的最后一个元素，即完成反转
        next = cur->next;       // 让next指向3号节点
        cur->next = next->next;      // 把4号节点接在cur节点后面
        next->next = pre->next;      // 把cur节点接在next节点后面
        pre->next = next;            // 把next节点接在pre节点后面
    }                           // 至此，把新遇到的next节点接在了最前面
    return dummyNode->next;     // 反复循环到反转区间的最后一个元素，即完成整个反转
}

/*
逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
栈解法:
遇到数字入栈，遇到符号，出栈两个，进行运算后入栈，最后返回栈顶元素
*/
int LeeCode_07(vector<string>&tokens) 
{
    stack<int>s;
    int l=0;            // 创建一个中间变量 l
    for(int i=0;i<tokens.size();i++)
    {
        char ch=tokens[i][0];   // 检查是否为符号，若字符串长度超过1，则有可能是负数
        if(!isdigit(tokens[i][0])&&tokens[i].length()<2)
        {
            l=s.top();          // 根据不同的符号进行不同的运算
            s.pop();
            switch(ch)
            {
                case '+':
                {
                    s.top()+=l;
                    break;
                }
                case '-':
                {
                    s.top()-=l;
                    break;
                }
                case '*':
                {
                    s.top()*=l;
                    break;
                }
                case '/':
                {
                    s.top()/=l;
                    break;
                }
            }
            l=0;
        }
        else
        {
            for(int j=0;j<tokens[i].length();j++)
            {               // 去除负号
                if(!isdigit(tokens[i][j]))
                {
                    continue;
                }
                l=l*10+int(tokens[i][j]-'0');
            }
            if(!isdigit(tokens[i][0]))  // 根据符号入栈操作
            {
                s.push(-1*l);
            }
            else
            {
                s.push(l);
            }
            l=0;
        }
    }               // 最后返回栈顶元素
    return s.top();
}

/*
矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
设置一个二维数组，记录每一个为 0 数值的位置，然后根据位置逐个置零
*/
void LeeCode_08(vector<vector<int>> &matrix)
{               // 用vector 设置二维数组，其值自动置零，方便操作
    vector<int>x(matrix.size()),y(matrix[0].size());
    for(int i=0;i<matrix.size();i++)
    {
        for(int j=0;j<matrix[0].size();j++)
        {
            if(matrix[i][j]==0)
            {               // 遍历数组并记录为0的下标
                x[i]=1;
                y[j]=1;
            }
        }
    }
    for(int i=0;i<matrix.size();i++)
    {                       // 根据记录的位置，再次遍历逐个置零
        for(int j=0;j<matrix[0].size();j++)
        {
            if(x[i]==1||y[j]==1)
            {
                matrix[i][j]=0;
            }
        }
    }
}

/*
位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式）
返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）
输入：00000000000000000000000000001011
输出：3
理解二进制数的 与操作，左移右移
左右移等位运算符是在转化为二进制下的运算
<<左移
将位数向左移动，相当于乘以2
如:10左移8位变成512,二进制为10变成10 0000 0000
>>右移
将位数向右移动，相当于除以2
如:2048右移8位变成8,二进制为1000 0000 0000变成1000
&与运算 (取交集，交集不为0，则为真)
两个操作数中位都为1，结果才为1，否则结果为0
如:240&60结果为48,二进制为1111 0000 & 11 1100 结果 11 0000
|或运算  (取并集，并集不为0，则为真)
两个位只要有一个为1，那么结果就是1，否则就为0
如:252|60结果为252,二进制为1111 0000 | 11 1100 结果 1111 1100
^ 异或运算 (二进制下对比，相同位取0，不同位取1)
2 ^ 4 即 00000010 ^ 00000100 =00000110 ，所以 2 ^ 4 的值为6
负数的二进制用其绝对值的补码表示，补码=反码+1，反码=原码取反
*/
int LeeCode_09_01(uint32_t n) 
{
    int num=0;
    for(int i=0;i<32;i++)
    {          // 1 不断的左移，和n做与操作，只有当n的第i位不为0时，也就是有交集，结果为真
        if(n&(1<<i))
        {
            num++;
        }
    }
    return num;
}
int LeeCode_09_02(uint32_t n) 
{
    int num=0;
    while(n)
    {         // 去掉二进制数的最后一个1，n-1向上借位，去掉最后一个1，新加一个1，后与原来的做与操作
        n&(n-1);    // 去除新加的1，最终达到去掉原数中最后一个1的目的
        num++;      // 当1都去掉了，n==0，循环结束
    }
    return num;
}


/*
删除排序链表中重复的元素II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点
只保留原始链表中 没有重复出现 的数字，返回同样按升序排列的结果链表
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
建立一个头指针，一个计数指针，从头开始遍历
计数指针起初指向头指针，之后每次比较计数指针的后两个
值相同，继续向后指，直到值不同
值不同，计数指针向后移动一位，最后返回头指针的下一个节点
*/
ListNode* LeeCode_10(ListNode* head) 
{
    if(!head)   // 判断是否为空指针
    {
        return head;
    }                      // 创建头指针，next域指向head
    ListNode *l=new ListNode(-1,head); 
    ListNode *c=l;          // 创建计数指针
    while(c->next&&c->next->next)  // 每次比较计数指针的后两位，所以不能为空
    {           // 比较计数指针后两位
        if(c->next->val==c->next->next->val)
        {               // 记录相同的值
            int i=c->next->val;         // 0    1   2   3   4
            while(c->next&&c->next->val==i)  // c->next为空时，表示已到表尾，否则循环到值不相同
            {               // 计数指针的next域后移一位
                c->next=c->next->next;
            }
        }
        else
        {               // 值不同，计数指针后移一位
            c=c->next;
        }
    }           // 返回新的链表
    return l->next;
}


/*
存在重复元素II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j
使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k
输入: nums = [1,2,3,1], k = 3
输出: true
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
利用哈希表，即无法放入重复元素，当新的元素在容器中已经存在时，且计数器<k，即为真
*/
bool LeeCode_11(vector<int>& nums, int k) 
{                   // 创建一个map容器，无法放入重复元素
    map<int,int>m;
    for(int i=0;i<nums.size();i++)
    {               // 检测容器中是否存在 nums[i]的键值，若存在即为真
        if(m.count(nums[i]))
        {
            return true;
        }                   //m[nums[i]]=i;     插入元素
        m.insert(make_pair(nums[i],i));
        if(m.size()>k)      // 如果容器大小超过k，即删除第一个元素，继续检测第二个元素
        {
            m.erase(nums[i-k]);
        }
    }
    return false;
}


/*
七进制数
给定一个整数，将其转化为7进制，并以字符串形式输出，包含负数
输入: 100
输出: "202"
*/
string LeeCode_12_01(int num) 
{           // 转七进制，递归算法
    if (num < 0) return "-" + LeeCode_12_01(-1 * num);  // 小于0，前面加个负号，之后一直按正数计算
    if (num < 7) return to_string(num);         // 小于7，直接返回到最后一位
    return LeeCode_12_01(num / 7) + to_string(num % 7);
}          // 高位放在后面，低位除出来放在高位



/*
旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
先将单向链表改成环表，头指针指向移动后的第一个元素，最后把循环表改成单向链表
r->next指向最终链表的的一个元素，r指向最终链表的最后一个元素
最后的操作就是，置空r的next域，恢复成单向链表
移动k个位置，即链表最后的K个元素都要移到链表前面来，需要定位到移动后的首元素
即链表中i-k位置的元素，r不断的右移(i-k)次数，使得r->next指向它
*/
ListNode* LeeCode_12_02(ListNode* head, int k) 
{       // 当head是空指针或者不移动又或者只有一个元素的时候，直接返回head
    if(!head||k==0||(!(head->next)))return head;
    int i=1;            // 记录 链表中元素个数
    ListNode *l=new ListNode(-1,head);  // 建立两个头指针
    ListNode *r=l;
    while(head->next)
    {
        head=head->next;    // head指向；链表的最后一个节点
        i++;        // 记录个数，并找到最后一个节点
    }
    head->next=l->next;     // 最后指向开头形成环表
    if(i<k)k=k%i;          // 要移动的步数大于链表长度时，取模
    if(k==i)            // 移动步数等于链表长度时，不移动，改回成单向链表，直接返回原链表
    {
        head->next=NULL;
        return l->next;
    }                   // 定位到移动后的第一个元素，头指针L指向它
    for(int j=1;j<=i-k;j++)r=r->next;
    l->next=r->next;
    r->next=NULL;       // 改回成单向链表
    return l->next;
}


/*
二叉搜索树迭代器
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象
BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字
且该数字小于 BST 中的任何元素
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 
int next()将指针向右移动，然后返回指针处的数字
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字
输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
创建一个数组，存储二叉树的中序遍历顺序
next，hasNext返回数组中的相关信息
*/
class BSTIterator_LeeCode_13
{
public:         // 递归中序遍历，顺序存储在数组中
    void traverse(TreeNode* root,vector<int>&res)
    {
        if(!root)
        {
            return;
        }
        traverse(root->left,res);
        res.push_back(root->val);   // 根值放中间代表，中序遍历
        traverse(root->right,res);
    }       // 返回值，不要返回引用，因为要用另外一个变量去接收它，返回变量就无法用变量接受
    vector<int> mediation(TreeNode* root)
    {
        vector<int>res;
        traverse(root,res);
        return res;
    }
    vector<int> arr;
    int idx;        // idx 记录已经从数组中读取出来的个数
    BSTIterator_LeeCode_13(TreeNode* root):idx(0),arr(mediation(root)){}
    int next() 
    {           // 直接按照中序遍历的顺序返回值
        return arr[idx++];
    }
    bool hasNext() 
    {
        return (idx<arr.size());
    }
};


/*
给定一个段落 (paragraph) 和一个禁用单词列表 (banned)。返回出现次数最多，同时不在禁用列表中的单词
输入: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
输出: "ball"
利用非重复容器unordered_set、unordered_map，插入到容器中记录下所有的禁用单词
遍历段落，遇到一个非字母即为一个单词，在容器查找，看是否是禁用单词
不是则加入到另一容器中，并且次数加一，最后返回次数最多的单词
遍历完后，得考虑最后一个单词，如果不是以非字母结束，最后一个单词将不会被判断
只要sl长度大于零，说明还有一个单词，需要判断
*/
string mostCommonWord(string paragraph, vector<string>& banned) 
{
    unordered_set<string>se;
    unordered_map<string,int>ma;
    int max=0;
    string mas="";
    string sl="";
    for(auto c:banned)
        se.insert(c);
    for(auto c:paragraph)
    {
        if(isalpha(c))
        {
            sl+=tolower(c);
        }
        else if(sl.size()>0)
        {
            if(se.find(sl)==se.end())
            {
                ma[sl]++;
                if(ma[sl]>max)
                {
                    max=ma[sl];
                    mas=sl;
                }
            }
            sl="";
        }
    }
    if(se.find(sl)==se.end()&&sl.size()>0)
    {
        ma[sl]++;
        if(ma[sl]>max)
        {
            max=ma[sl];
            mas=sl;
        }
    }
    return mas;
}


/*
翻转字符串，双指针，遇到非字符位置不动
如"sh-ios-kl=you"--"uo-ylk-so-ihs"
用两个指针，分别指向头尾，不断向中间走，遇到非字母则跳过，两边都是字母的情况则交换
直到头尾指针相交
*/
string reverseOnlyLetters(string s) 
{
    char tmp;
    int left=0;
    int right=s.length()-1;
    while(left<right)
    {
        if(isalpha(s[left])&&isalpha(s[right]))
        {
            tmp=s[left];
            s[left]=s[right];
            s[right]=tmp;
            left++;
            right--;
        }
        if(!isalpha(s[left]))
        {
            left++;
        }
        if(!isalpha(s[right]))
        {
            right--;
        }
    }
    return s;
}


/*
字符串偏移问题
编写一个函数，作用是把一个char组成的字符串循环右/左移n个
比如原来是“abcdefghi”如果n=2，移位后应该是“hiabcdefg”
void LoopMove ( char * pStr, int steps )
{
    int n=strlen(pStr)-steps;
    char temp[strlen(pStr)+1];--+1是因为尾部有'\0'作结束符
    strcpy(temp,pStr+n);--切出要前移的片段
    temp+strlen(pStr)='\0';--去除尾部多余的部分
    strcpy(temp+steps,pStr);--将头部与前移的片段接上
    pStr=temp;--完成替换
}
*/